package demo.practice.binary_search;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class P167 {


    public static void main(String[] args) {
        P167 p167= new P167();
        p167.twoSum(new int[]{5,25,75},100);
    }

    public int[] twoSum(int[] numbers, int target) {
        //思路1  最简单的轮询  两层循环  arr[i]+arr[j] == target 则  返回i,j
        //思路2  仅一层循环，先假设  arr[i]+x==target 能成立  map.push(x,i)，每次遍历的时候先检验arr[i]是否存在于map中
        //时间复杂度O(n)
        //思路3  二分搜索法  在i+1 到 arr.length-1的范围内去搜索   target-arr[i]
        //时间复杂度O(n*logn)
        //思路4   双指针，因为numbers 是有序的。所以如果 arr[i]+arr[j]==target 那么有  arr[0~i)+arr[j]<target
        //     arr[i]+arr(j~arr.length-1]>target

       /* Map<Integer,Integer> map= new HashMap();
        for(int i=0;i<numbers.length;i++){
            if(map.containsKey(numbers[i]))
                return new int[]{map.get(numbers[i])+1,i+1};
            map.put(target-numbers[i],i);
        }
        return new int[]{-1,-1};*/


        int i = 0;
        int j = numbers.length - 1;

        while (i < j) {
            if (numbers[i] + numbers[j] == target)
                return new int[]{i + 1, j + 1};
            if (numbers[i] + numbers[j] > target) {
                j--;
            }else {
                i++;
            }
        }

        return new int[]{-1, -1};


    }
}
